﻿namespace Leetcode.N0762;

public class Solution
{
    public int CountPrimeSetBits(int left, int right)
    {
        var count = 0;
        for (var i = left; i <= right; i++)
        {
            var bCount = this.GetByteCount(i);
            if (this.IsPrime(bCount))
            {
                count++;
            }
        }
        return count;

    }

    int GetByteCount(int value)
    {
        var count = 0;
        while (value != 0)
        {
            value &= value - 1;
            count++;
        }
        return count;
    }

    bool IsPrime(int x)
    {
        if (x <= 1)
        {
            return false;
        }

        for (int i = 2; i * i <= x; ++i)
        {
            if (x % i == 0)
            {
                return false;
            }
        }
        return true;
    }
}
